《剑指offer》JavaScript版——(4)重建二叉树

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：
前序遍历的第一个节点就是根节点，中序遍历根节点的左边在根节点的左子树，右边在根节点的右子树。

/* function TreeNode(x) {
   this.val = x;
   this.left = null;
   this.right = null;
} */
function reConstructBinaryTree(pre, vin) {
   if(pre.length == 0 || vin.length == 0) {
      return null;
   }
   var idx = vin.indexOf(pre[0]);    // 根节点的索引  
   
   var vinleft = vin.slice(0, idx);  // 中序左子树
   var vinright = vin.slice(idx+1);  // 中序右子树  
   
   var preleft = pre.slice(1,idx+1); // 前序左子树
   var preright = pre.slice(idx+1);  // 前序右子树    
   return {
      val: pre[0],
      left: reConstructBinaryTree(preleft, vinleft),  // 递归
      right: reConstructBinaryTree(preright, vinright)
   }
}